package structures.linklist;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class SimpleLinkListDemo {
    public static void main(String[] args) {
        SingleLinkList singleLinkList = new SingleLinkList();
//        singleLinkList.addNode(new HeroNode(1, "宋江", "songjiang"));
//        singleLinkList.addNode(new HeroNode(4, "武松", "wusong"));
//        singleLinkList.addNode(new HeroNode(3, "鲁智深", "luzhishen"));
        singleLinkList.addNoteByNum(new HeroNode(1, "宋江", "songjiang"));
        singleLinkList.addNoteByNum(new HeroNode(4, "武松", "wusong"));
        singleLinkList.addNoteByNum(new HeroNode(3, "鲁智深", "luzhishen"));
        singleLinkList.addNoteByNum(new HeroNode(2, "2智深", "2luzhishen"));
        singleLinkList.addNoteByNum(new HeroNode(2, "22智深", "22luzhishen"));
        singleLinkList.showHeroListInfo();
        singleLinkList.updateNodeByNum(4, new HeroNode(4, "武松2", "wusong2"));
        singleLinkList.showHeroListInfo();
        System.out.println("----------------");
        singleLinkList.deleteNodeByNum(4);
        singleLinkList.showHeroListInfo();
        System.out.println("显示链表数量 --> " + singleLinkList.getLinkListCount());
        System.out.println("----------------");
        System.out.println(singleLinkList.getNodeByOrder(0));
        System.out.println("----------------");
        singleLinkList.reverse();
        singleLinkList.showHeroListInfo();
        System.out.println("----------------");
        singleLinkList.reverse2();
        singleLinkList.showHeroListInfo();
        System.out.println("----------------");
        singleLinkList.printByOrder();
        System.out.println("----------------");
    }
}

class SingleLinkList {
    // 创建头结点
    private final HeroNode head = new HeroNode(0, "", "");

    // 添加结点
    public void addNode(HeroNode newNode) {
        HeroNode node = getHeadNode();
        while (node.getNext() != null) {
            node = node.getNext();
        }
        node.setNext(newNode);
    }

    public void addNoteByNum(HeroNode newNode) {
        // 获取头结点以及下一个结点, 如果没有下一个结点 则直接加入
        HeroNode node = getHeadNode();
        HeroNode nextNode = null;
        if (node.getNext() == null) {
            node.setNext(newNode);
            return;
        } else {
            nextNode = node.getNext();
        }

        // 判断新建的结点num是都在两者之间
        while (nextNode != null) {
            if (nextNode.getNum() > newNode.getNum()
                    && node.getNum() <= newNode.getNum()) {
                // 如果在两个node之间,则直接插入
                node.setNext(newNode);
                newNode.setNext(nextNode);
                return;
            } else {
                // 不在两者之间则继续往下查找
                node = nextNode;
                nextNode = nextNode.getNext();
            }
        }
        // 不在节点之间就添加在最后
        node.setNext(newNode);
    }

    // 显示所有节点信息
    public void showHeroListInfo() {
        HeroNode node = getHeadNode();
        // 判断除了head结点是否还有其他结点
        if (node.getNext() == null) return;
        else node = node.getNext();

        while (node != null) {
            System.out.println(node);
            node = node.getNext();
        }
        System.out.println("显示完毕...");
    }

    // 通过num修改 node  但是不修改 num值
    public boolean updateNodeByNum(int num, HeroNode newNode) {
        HeroNode node = getHeadNode();
        while (node.getNext() != null) {
            node = node.getNext();
            if (node.getNum() == num) {
                node.setName(newNode.getName());
                node.setNick(newNode.getNick());
                return true;
            }
        }
        return false;
    }

    public boolean deleteNodeByNum(int num) {
        HeroNode node = getHeadNode();
        while (node.getNext() != null) {
            if (node.getNext().getNum() == num) {
                HeroNode tempNode = node.getNext();
                node.setNext(node.getNext().getNext());
                tempNode.setNext(null);
                return true;
            }
            node = node.getNext();
        }
        return false;
    }

    //  获取头结点
    public HeroNode getHeadNode() {
        return head;
    }

    // 面试题1   求单链表的有效节点数量 --> 其实就是遍历啦
    public int getLinkListCount() {
        HeroNode node = getHeadNode();
        int count = 0;
        while (node.getNext() != null) {
            node = node.getNext();
            count++;
        }
        return count;
    }

    // 面试2 查找单链表倒数第N个节点  --> 在面试1的基础上进行处理
    public HeroNode getNodeByOrder(int n) {
        int count = getLinkListCount();
        HeroNode node = getHeadNode();
        if (n > count || n < 0) return null;
        for (int index = 0; index < count - n; index++) {
            node = node.getNext();
            if (node == null) return null;
        }
        return node;
    }

    // 面试3 单链表的翻转 我的思维是遍历链表放入List中  然后反向遍历List组成新的翻转链表
    // 老师给的方法是头插法  就是遍历原来的链表 遍历出的每个点都将其去除放入新建节点的前面,这个方式好像更更好一些~
    public void reverse() {
        List<HeroNode> heroNodeList = new ArrayList<>();
        HeroNode node = getHeadNode();
        if (node.getNext() == null) return;
        // 遍历 存入List
        while (node.getNext() != null) {
            heroNodeList.add(node.getNext());
            node = node.getNext();
        }

        // 反转链表
        HeroNode newNode = getHeadNode();
        for (int i = heroNodeList.size() - 1; i >= 0; i--) {
            heroNodeList.get(i).setNext(null);
            newNode.setNext(heroNodeList.get(i));
            newNode = newNode.getNext();
        }
    }

    // 使用老师想到的头插法
    public void reverse2() {
        HeroNode headNode = getHeadNode();
        HeroNode node = headNode.getNext();
        // 此处重新定义一个头是为了定义一个缓存
        if (headNode.getNext() == null ||
                node.getNext() == null) return;

        // 这一句很重要! 防止最后无限循环
        headNode.setNext(null);

        while (node != null) {
            HeroNode tempNode = node.getNext();
            node.setNext(headNode.getNext());
            headNode.setNext(node);
            node = tempNode;
        }
    }

    // 逆向打印
    // 我的想法
    // 1. 遍历链表存入list 然后逆向遍历list打印
    // 2. 用上面的反转链表 然后打印  但是这样会破坏链表顺序 需要在执行一次逆序还原链表
    // 3. 老师推荐: 利用栈 将各个节点压入栈中,然后利用栈先入后出的特点实现逆序打印 其实与方式1的操作差不多..
    public void printByOrder() {
        Stack<HeroNode> heroNodeStack = new Stack<>();
        HeroNode node = getHeadNode();

        if (node.getNext() == null) return;

        // 入栈
        while (node.getNext() != null) {
            node = node.getNext();
            heroNodeStack.push(node);
        }

        // 出栈
        while (heroNodeStack.size() > 0) {
            System.out.println(heroNodeStack.pop());
        }

    }
}

class HeroNode {
    private int num;
    private String name;
    private String nick;
    private HeroNode next;

    public HeroNode(int num, String name, String nick) {
        this.num = num;
        this.name = name;
        this.nick = nick;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNick() {
        return nick;
    }

    public void setNick(String nick) {
        this.nick = nick;
    }

    public HeroNode getNext() {
        return this.next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", nick='" + nick + '\'' +
                '}';
    }
}


